#include <iostream>
#include <stack>    // 包含标准库栈
#include <queue>
// #include <dueue.h>
#include <deque>

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {

        std::deque<int> qqq;
        while (head != nullptr) {
            qqq.push_back(head->val);
            std::cout << head->val << std::endl;
            head = head->next;
        }

        ListNode* ret_list = new ListNode(qqq.back());
        qqq.pop_back();

        ListNode* iii = ret_list;
        while (!qqq.empty()) {
            ListNode* iiii = new ListNode(qqq.back());
            qqq.pop_back();
            iii->next = iiii;
            std::cout << iii->val << std::endl;
            iii = iii->next;
        }
        return ret_list;

    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList1(ListNode* head) {
        ListNode* ret_list = nullptr;

        while (head != nullptr) {
            ListNode* tamp = head->next;
            
            head->next = ret_list;

            ret_list = head;

            head = tamp;
        }

        return ret_list;
    }
};


// 打印链表的函数
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}


// main 函数
int main(int argc, char **argv) {
    // 创建链表 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    std::cout << "Original list: ";
    printList(head);

    // 反转链表
    Solution solution;
    ListNode* reversedHead = solution.ReverseList(head);

    std::cout << "Reversed list: ";
    printList(reversedHead);

    // 释放内存
    while (reversedHead != nullptr) {
        ListNode* temp = reversedHead;
        reversedHead = reversedHead->next;
        delete temp;
    }

    return 0;
}